OcrV1, Main, Exploration, bibRecord, 001359

A Faster and Simpler 2-Approximation Algorithm for Block Sorting

Identifieur interne : 001359 ( Main/Exploration ); précédent : 001358; suivant : 001360

A Faster and Simpler 2-Approximation Algorithm for Block Sorting

Auteurs : W. Bein [États-Unis] ; L. Larmore [États-Unis] ; Linda Morales [États-Unis] ; Hal Sudborough [États-Unis]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2005.

RBID : ISTEX:876886ECBB532E654E5252BCC6A9FE8217AD582E

Descripteurs français

Pascal (Inist)
- Algorithme approximation, Informatique théorique, Méthode heuristique, Problème NP difficile, Reconnaissance caractère, Reconnaissance optique caractère, Triage.

English descriptors

KwdEn :
- Approximation algorithm, Character recognition, Computer theory, Heuristic method, NP hard problem, Optical character recognition, Sorting.

Abstract

Abstract: Block sorting is used in connection with optical character recognition (OCR). Recent work has focused on finding good strategies which perform well in practice. Block sorting is $\mathcal{NP}$ -hard and all of the previously known heuristics lack proof of any approximation ratio. We present here an approximation algorithm for the block sorting problem with approximation ratio of 2 and run time O(n 2). The approximation algorithm is based on finding an optimal sequence of absolute block deletions.

Url:

https://api.istex.fr/document/876886ECBB532E654E5252BCC6A9FE8217AD582E/fulltext/pdf

DOI: 10.1007/11537311_11

Affiliations:

États-Unis
Nevada, Texas

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Faster and Simpler 2-Approximation Algorithm for Block Sorting</title>
<author><name sortKey="Bein, W" sort="Bein, W" uniqKey="Bein W" first="W." last="Bein">W. Bein</name>
</author>
<author><name sortKey="Larmore, L" sort="Larmore, L" uniqKey="Larmore L" first="L." last="Larmore">L. Larmore</name>
</author>
<author><name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
</author>
<author><name sortKey="Sudborough, Hal" sort="Sudborough, Hal" uniqKey="Sudborough H" first="Hal" last="Sudborough">Hal Sudborough</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:876886ECBB532E654E5252BCC6A9FE8217AD582E</idno>
<date when="2005" year="2005">2005</date>
<idno type="doi">10.1007/11537311_11</idno>
<idno type="url">https://api.istex.fr/document/876886ECBB532E654E5252BCC6A9FE8217AD582E/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000E97</idno>
<idno type="wicri:Area/Istex/Curation">000E56</idno>
<idno type="wicri:Area/Istex/Checkpoint">000C68</idno>
<idno type="wicri:doubleKey">0302-9743:2005:Bein W:a:faster:and</idno>
<idno type="wicri:Area/Main/Merge">001395</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:05-0407947</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000444</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000343</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000442</idno>
<idno type="wicri:doubleKey">0302-9743:2005:Bein W:a:faster:and</idno>
<idno type="wicri:Area/Main/Merge">001472</idno>
<idno type="wicri:Area/Main/Curation">001359</idno>
<idno type="wicri:Area/Main/Exploration">001359</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Faster and Simpler 2-Approximation Algorithm for Block Sorting</title>
<author><name sortKey="Bein, W" sort="Bein, W" uniqKey="Bein W" first="W." last="Bein">W. Bein</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>School of Computer Science, University of Nevada, 89154, Las Vegas, Nevada</wicri:regionArea>
<placeName><region type="state">Nevada</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Larmore, L" sort="Larmore, L" uniqKey="Larmore L" first="L." last="Larmore">L. Larmore</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>School of Computer Science, University of Nevada, 89154, Las Vegas, Nevada</wicri:regionArea>
<placeName><region type="state">Nevada</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Computer Science Department, Texas A&M University-Commerce, 75429, Commerce, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Sudborough, Hal" sort="Sudborough, Hal" uniqKey="Sudborough H" first="Hal" last="Sudborough">Hal Sudborough</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, University of Texas at Dallas, 75083, Richardson, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2005</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">876886ECBB532E654E5252BCC6A9FE8217AD582E</idno>
<idno type="DOI">10.1007/11537311_11</idno>
<idno type="ChapterID">11</idno>
<idno type="ChapterID">Chap11</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Character recognition</term>
<term>Computer theory</term>
<term>Heuristic method</term>
<term>NP hard problem</term>
<term>Optical character recognition</term>
<term>Sorting</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Algorithme approximation</term>
<term>Informatique théorique</term>
<term>Méthode heuristique</term>
<term>Problème NP difficile</term>
<term>Reconnaissance caractère</term>
<term>Reconnaissance optique caractère</term>
<term>Triage</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Block sorting is used in connection with optical character recognition (OCR). Recent work has focused on finding good strategies which perform well in practice. Block sorting is $\mathcal{NP}$ -hard and all of the previously known heuristics lack proof of any approximation ratio. We present here an approximation algorithm for the block sorting problem with approximation ratio of 2 and run time O(n 2). The approximation algorithm is based on finding an optimal sequence of absolute block deletions.</div>
</front>
</TEI>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Nevada</li>
<li>Texas</li>
</region>
</list>
<tree><country name="États-Unis"><region name="Nevada"><name sortKey="Bein, W" sort="Bein, W" uniqKey="Bein W" first="W." last="Bein">W. Bein</name>
</region>
<name sortKey="Bein, W" sort="Bein, W" uniqKey="Bein W" first="W." last="Bein">W. Bein</name>
<name sortKey="Larmore, L" sort="Larmore, L" uniqKey="Larmore L" first="L." last="Larmore">L. Larmore</name>
<name sortKey="Larmore, L" sort="Larmore, L" uniqKey="Larmore L" first="L." last="Larmore">L. Larmore</name>
<name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
<name sortKey="Morales, Linda" sort="Morales, Linda" uniqKey="Morales L" first="Linda" last="Morales">Linda Morales</name>
<name sortKey="Sudborough, Hal" sort="Sudborough, Hal" uniqKey="Sudborough H" first="Hal" last="Sudborough">Hal Sudborough</name>
<name sortKey="Sudborough, Hal" sort="Sudborough, Hal" uniqKey="Sudborough H" first="Hal" last="Sudborough">Hal Sudborough</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001359 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001359 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Ticri/CIDE
   |area=    OcrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:876886ECBB532E654E5252BCC6A9FE8217AD582E
   |texte=   A Faster and Simpler 2-Approximation Algorithm for Block Sorting
}}

This area was generated with Dilib version V0.6.32.
Data generation: Sat Nov 11 16:53:45 2017. Site generation: Mon Mar 11 23:15:16 2024

Serveur d'exploration sur l'OCR

A Faster and Simpler 2-Approximation Algorithm for Block Sorting

A Faster and Simpler 2-Approximation Algorithm for Block Sorting

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur l'OCR
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.